BZOJ3676【NOI2015】品酒大会 <后缀数组+并查集>

Problem

BZOJ3676【NOI2015】品酒大会

Time Limit:
Memory Limit:

Description

一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战两个环节，分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项，吸引了众多品酒师参加。
在大会的晚餐上，调酒师调制了杯鸡尾酒。这杯鸡尾酒排成一行，其中第杯酒被贴上了一个标签，每个标签都是个小写英文字母之一。设表示第杯酒到第杯酒的个标签顺次连接构成的字符串。若，其中，，，，则称第杯酒与第杯酒是“ 相似”的。当然两杯“ 相似” 的酒同时也是“ 相似”、“ 相似”、……、“ 相似”的。特别地，对于任意的，第杯酒和第杯酒都是“ 相似”的。
在品尝环节上，品酒师轻松地评定了每一杯酒的美味度，凭借其专业的水准和经验成功夺取了“首席品酒家”的称号，其中第杯酒的美味度为。现在公布了挑战环节的问题：本次大会调制的鸡尾酒有一个特点，如果把第杯酒与第杯酒调兑在一起，将得到一杯美味度为的酒。现在请各位品酒师分别对于，统计出有多少种方法可以选出杯“ 相似”的酒，并回答选择杯“相似”的酒调兑可以得到的美味度的最大值。

Input

第行包含个正整数，表示鸡尾酒的杯数。
第行包含一个长度为的字符串，其中第 i 个字符表示第杯酒的标签。
第行包含个整数，相邻整数之间用单个空格隔开，其中第个整数表示第杯酒的美味度。

Output

输出文件包括行。第行输出个整数，中间用单个空格隔开。第个整数表示选出两杯“ 相似”的酒的方案数，第个整数表示选出两杯“ 相似”的酒调兑可以得到的最大美味度。若不存在两杯“ 相似”的酒，这两个数均为。

Sample

Sample 1

Input

1
2
3

10
ponoiiipoi
2 1 4 7 4 8 3 6 4 7

Output

Explanation
二元组表示第杯酒与第杯酒。
相似：所有对二元组都是相似的，美味度最大的是。
相似：。
相似：4\times 8=323,4,5,\cdots ,90$。

Sample 2

Input

1
2
3

12
abaabaabaaba
1 -2 3 -4 5 -6 7 -8 9 -10 11 -12

Output

HINT

对于的数据，。
有的数据，不存在“ 相似”的酒。
有的数据，所有的值都相等。
对于的数据，。

标签：后缀数组 并查集

Solution

建后缀数组后统计每种的后缀对有哪些，发现当从高向低枚举相似度时，只会有越来越多的字符串满足，则每次合并新加进来的后缀对，用并查集维护。即若后缀和最高为相似，则从倒叙枚举到时把和所在的集合合并。

Code

#include <bits/stdc++.h>
#define MAX_N 300000
using namespace std;
typedef long long lnt;
int n, a[MAX_N+5];	char s[MAX_N+5];
int sa[MAX_N+5], rk[MAX_N+5], height[MAX_N+5], tsa[MAX_N+5], cntA[MAX_N+5], cntB[MAX_N+5], A[MAX_N+5], B[MAX_N+5];
lnt ans[MAX_N+5][2];	vector <int> m[MAX_N+5];	int fa[MAX_N+5], mina[MAX_N+5], maxa[MAX_N+5], size[MAX_N+5];
int getf(int x) {return x == fa[x] ? x : fa[x] = getf(fa[x]);}
void CalcSA() {
    for (int i = 1; i <= 26; i++) cntA[i] = 0;
    for (int i = 1; i <= n; i++) cntA[s[i]-'a'+1]++;
    for (int i = 1; i <= 26; i++) cntA[i] += cntA[i-1];
    for (int i = n; i >= 1; i--) sa[cntA[s[i]-'a'+1]--] = i;	rk[sa[1]] = 1;
    for (int i = 2; i <= n; i++) {rk[sa[i]] = rk[sa[i-1]];	if (s[sa[i]] != s[sa[i-1]]) rk[sa[i]]++;}
    for (int l = 1; l < n; l <<= 1) {
        for (int i = 1; i <= n; i++) cntA[i] = 0;	for (int i = 1; i <= n; i++) cntB[i] = 0;
        for (int i = 1; i <= n; i++) cntA[A[i] = rk[i]]++, cntB[B[i] = (i+l <= n) ? rk[i+l] : 0]++;
        for (int i = 1; i <= n; i++) cntB[i] += cntB[i-1];	for (int i = n; i >= 1; i--) tsa[cntB[B[i]]--] = i;
        for (int i = 1; i <= n; i++) cntA[i] += cntA[i-1];	for (int i = n; i >= 1; i--) sa[cntA[A[tsa[i]]]--] = tsa[i];
        rk[sa[1]] = 1;
        for (int i = 2; i <= n; i++) {
            rk[sa[i]] = rk[sa[i-1]];
            if (A[sa[i]] != A[sa[i-1]] || B[sa[i]] != B[sa[i-1]]) rk[sa[i]]++;
        }
    }
    for (int i = 1, j = 0; i <= n; i++) {
        if (j)	j--;
        while (s[i+j] == s[sa[rk[i]-1]+j]) j++;
        height[rk[i]] = j;
    }
}
int main() {
    scanf("%d", &n), scanf("%s", s+1);	lnt tot = 0, pro = 0;
    for (int i = 1; i <= n; i++) scanf("%d", a+i);	CalcSA();
    for (int i = 2; i <= n; i++) m[height[i]].push_back(i);
    for (int i = 1; i <= n; i++) fa[i] = i, size[i] = 1, mina[i] = maxa[i] = a[sa[i]];
    for (int i = n-1; ~i; i--) {
        for (int j = 0; j < (int)m[i].size(); j++) {
            int u = getf(m[i][j]), v = getf(m[i][j]-1);	if (u == v)	continue;
            if (!tot) pro = max(1LL*mina[u]*mina[v], 1LL*maxa[u]*maxa[v]);
            else pro = max(pro, max(1LL*mina[u]*mina[v], 1LL*maxa[u]*maxa[v]));
            tot += 1LL*size[u]*size[v], fa[v] = u, size[u] += size[v];
            mina[u] = min(mina[u], mina[v]), maxa[u] = max(maxa[u], maxa[v]);
        }
        ans[i][0] = tot, ans[i][1] = pro;
    }
    for (int i = 0; i < n; i++) printf("%lld %lld\n", ans[i][0], ans[i][1]);	return 0;
}